// 整理些算法常用工具方法

/**
 * 判断是否互质
 * @param {Int} a 第一个整数
 * @param {Int} b 第二个整数
 * @returns {false} 最大公约数是否为1
 */
function isCoprime(a, b) {
  let tmp
  while (true) {
    tmp = x % y
    if (tmp === 0) {
      break
    }
    x = y
    y = tmp
  }

  return y === 1 // 是否最大公约数为1
}

/**
 * @param  x {number}
 * @param  y {number}
 * @description 辗转相除法求两数最大公约数
 */
const gcd = function (x, y) {
  if (x < y) return gcd(y, x)
  while (true) {
    let z = x % y
    if (z === 0) {
      return y
    } else {
      x = y
      y = z
    }
  }
}

/**
 * @param  x {number}
 * @param  y {number}
 * @description stein除法求两数最大公约数
 * 思路:
 * 1. 若两个数都是偶数，则都除 >>1，记录次数；若两数为一奇一偶，则偶数 >>1 ；若两数均为奇数，则相减。
 * 2. 将得到的数重复执行步骤 1 直到得到的两个数相同。
 * 3. 若步骤 1 中两数都曾经 >>1，记录的次数为 n，则步骤 2 中得到的数再乘2n（<<n）即为两数的最大公约数。
 * 作用:超大数(比如64位以上)的除法计算代价较高,使用位运算能降低代价
 */
const gcd2 = function (x, y) {
  if (x == 0) {
    return y;
  } else if (y == 0) {
    return x;
  }
  while (y) {
    if (x < y) {
      let tmp = x;
      x = y;
      y = tmp;
    }
    if (x & 1 == 0) {
      if (y & 1 == 0) {
        x >>= 1;
        y >>= 1;
        count++; //计算两数均除2的次数
      } else {
        x >>= 1;
      }
    } else {
      if (y & 1 == 0) {
        y >>= 1;
      } else {
        let tmp = x - y;
        x = y;
        y = tmp; //y = 0 时while后的表达式为假，循环停止，得到x
      }
    }
  }
  return (x << count); //x再把两数同时除掉的2乘回来得到的数即为最大公约数

}

// JavaScript 刷题输入模板
var readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
  terminal: false
});

rl.on('line', function (line) {
  // code here
});


// 链表

// 结构
// Node : {
//   val:value,
//   next:Node
// }

// 获取后续链表
p1 = Node.next
// 前茶节点
Node.next = p1
// 后插节点
p1.next = Node

// 逆序  链表每一次遍历都会改变链表变量,需要提前备份
while (Node != null) {
  p1 = Node.next
  Node.next = p2
  p2 = Node
  Node = p1
}

// 逆序指定徐区间[m,n]
// start指向开始反转节点的前一个节点, 即 m - 1
// end指向 n + 1
let cur = head
let start = null
let end = null

// 寻找start和end
for (let i = 1; i <= n; i++) {
  if (i === m - 1) {
    start = cur
  }
  cur = cur.next
}
end = cur

let pre = null
let next = null
// 如果起始节点不是头节点，说明start有值
if (m > 1) {
  cur = start.next
  while (cur !== end) {
    next = cur.next
    cur.next = pre
    pre = cur
    cur = next
  }
  start.next.next = end
  start.next = pre
} else {
  // 起始节点就是头节点，start没有值
  cur = head
  while (cur !== end) {
    next = cur.next
    cur.next = pre
    pre = cur
    cur = next
  }
  head.next = end
  head = pre
}

// 链表的双重循环
while (head1 && head2) {
  if (falg) {
    head1 = head1.next
  } else {
    head2 = head2.next
  }
}

// 判断有无成环
// 双指针法,两指针步进分别1,2  若相遇即为成环
function hasCycle(head) {
  if (!head) {
    return head
  }
  let show = head
  let fast = head
  while (show && fast) {
    show = show.next
    if (fast.next) {
      fast = fast.next.next
    } else {
      return false
    }
    if (show == fast) {
      return true
    }
  }
  return false
}
// 字典法,遍历判断是否重复

// 找到环的起点
function EntryNodeOfLoop(head) {
  if (!head) {
    return head
  }
  let show = head
  let fast = head
  while (show && fast) {
    show = show.next
    if (fast.next) {
      fast = fast.next.next
    } else {
      break
    }
    if (show == fast) {
      break
    }
  }
  if (!fast || !fast.next) {
    return null
  }
  // 重新指向链表头部
  fast = head
  // 与第一次相遇的结点相同速度出发，相遇结点为入口结点
  // 这里步进相同,同时因为第一次相遇点
  while (fast != show) {
    fast = fast.next
    show = show.next
  }
  return fast
}

// 找到倒数k个节点
// 利用双指针,a指针先移动k步,再a,b指针同时移动.b指针移动到链表尾时,a指针就到了倒数k位置
// 处理了边界条件:k==0;k==length;pHead==null;
function FindKthToTail(pHead, k) {
  if (!pHead || !pHead.next || k == 0) return null;
  let h1 = pHead;
  let h2 = pHead;
  let i = 0;
  try {
    while (i < k) {
      h1 = h1.next;
      i++;
    }
  } catch (err) {
    return null;
  }
  if (h1) {
    while (h1) {
      h1 = h1.next;
      h2 = h2.next;
    }
    return h2;
  }
  return pHead;
}

// 删除倒数k节点
// 主要是找到倒数k+1节点,改变指向
function removeNthFromEnd(head, n) {
  if (n == 0) return head.next;
  if (!head || !head.next) return null;
  let node = FindKthToTail(head, n + 1);
  if (!node) {
    return head.next;
  } else if (node.next) {
    node.next = node.next.next;
  }
  return head;
}


// 两个链表的第一个公共结点
// 两个无环单链表相交时,头指头遍历过程中,利用非相交部分的路程和相等可得到等式
function FindFirstCommonNode(pHead1, pHead2) {
  let l1 = pHead1;
  let l2 = pHead2;
  while (l1 != l2) {
    l1 = l1 == null ? pHead2 : l1.next;
    l2 = l2 == null ? pHead1 : l2.next;
  }
  return l1;
}

// 判断回文:翻转一半和另一半比较

// 删除重复元素,仅保留未重复  递归
function deleteDuplicates(head) {
  if (head == null) {
    return null;
  }
  if (head.next != null && head.val == head.next.val) {
    //发现有重复值
    while (head.next != null && head.val == head.next.val) {
      head = head.next; //删除
    }
    return deleteDuplicates(head.next); //把与删除的那个结点相同的结点也进行删除
  }
  head.next = deleteDuplicates(head.next); //当没有发现重复值的情况，就一直进行递归操作
  return head;
}

// 二分法 从排序数组中找位置
// 需要三个变量表示下标
function search(nums, target) {
  let left = 0
  let right = nums.length - 1
  let middle = parseInt((left + right) / 2)
  // 判断条件能过滤空数组
  while (left <= right) {
    if (nums[middle] < target) {
      left = middle + 1
      middle = parseInt((left + right) / 2)
    } else if (nums[middle] > target) {
      right = middle - 1
      middle = parseInt((left + right) / 2)
    } else {
      return middle
    }
  }
  return -1
}


// 先序遍历: 根-> 左节点 -> 右节点
// 后序遍历: 左节点 -> 右节点 ->  根
// 后序遍历: 左节点 ->  根 -> 右节点 
// 根节点位置决定


// Q: 给定有向无环图G,如何计算两点s,t之间的简单路劲个数?




// 两超大整形字符串相加
function solve(s, t) {
  let len1 = s.length - 1;
  let len2 = t.length - 1;
  if (len1 < len2) {
    return solve(t, s);
  }
  if (len2 == -1) {
    return s;
  }
  let sign = 0;
  let res = "";
  // 循环从长开始能避免剩余的字符串与进位相加变成另一个规模较小的子问题
  while (len1 >= 0) {
    let _c = parseInt(s[len1]) + parseInt(t[len2] || '0') + sign;
    res = (_c % 10) + res;
    sign = Math.floor(_c / 10);
    len1--
    len2--
  }
  if (sign > 0) {
    res = 1 + res
  }
  return res;
}


// 奇数正序,偶数逆序,合并  要求原址排序,O(n)
// 算是链表逆序的拓展,有几个易错点
function reorderList(head) {
  if (!head || !head.next) {
    return head;
  }
  // 偶数逆序的初始化,因为逆序从2开始,1的后续需手动处理
  let h1 = head.next;
  if (head.next.next) {
    head.next = head.next.next;
  }
  let p1 = null;
  let p2 = null;
  if (h1) {
    while (h1 != null) {
      p1 = h1.next && h1.next.next;
      // 注意点1: 偶数部分要逆序,奇数结点被打散了,需要手动维护前后关系.不加这个所有奇数结点都找不到了
      if (h1.next && h1.next.next) {
        h1.next.next = h1.next.next.next;
      }
      // 注意点2: 这里next是指单独逆序部分的后续,与题意的间隔无关 写成h1.next.next就出问题了
      h1.next = p2;
      p2 = h1;
      h1 = p1;
    }
  }
  let h2 = null;
  let tail = null
  while (head != null && p2 != null) {
    let node1 = head;
    head = head.next;
    let node2 = p2;
    p2 = p2.next;
    node1.next = node2;
    if (!h2) {
      h2 = node1;
    } else {
      // 注意点3  需要一个变量找到新链表的尾部,已插入后续结点
      tail.next = node1;
    }
    tail = node2
  }
  if (head) {
    tail.next = head;
  }
  return h2;
}

//通过快慢指针,将链表对半分,奇数时,前半部分多一个
function midChain(head) {
  let slow = head;
  let fast = head;
  while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  let newHead = slow.next;
  slow.next = null;
  return [head, newHead];
}


// 计算二叉树所有根节点到叶子的简单路径构成的数字和,每个结点关键字在0-9之间
// 本质是考察深度优先遍历,需要注意的是sum和path变量
// sum需要在每次递归保留结果并用于输出
// path则在处理完下一个递归后应当复原,清除上个对下个递归和当前递归的影响
// 与此同类问题有九宫格的计算
function sumNumbers(root) {
  if (!root) return 0
  let sum = {
    val: 0
  };
  let path = root.val + ''

  function cal(node, path, sum) {
    if (node.left) {
      path += node.left.val
      cal(node.left, path, sum)
      path = path.substr(0, path.length - 1)
    }
    if (node.right) {
      path += node.right.val
      cal(node.right, path, sum)
      path = path.substr(0, path.length - 1)
    }
    if (!node.left && !node.right) {
      sum.val += parseInt(path)
    }
  }
  cal(root, path, sum)
  return sum.val
}


// 计算二叉树任一条路径上关键字和的最大值
function maxPathSum(root) {
  let maxSum = -Integer;

  function maxGain(node) {
    if (node == null) {
      return 0;
    }

    // 递归计算左右子节点的最大贡献值
    // 只有在最大贡献值大于 0 时，才会选取对应子节点
    let leftGain = Math.max(maxGain(node.left), 0);
    let rightGain = Math.max(maxGain(node.right), 0);

    // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
    let priceNewpath = node.val + leftGain + rightGain;

    // 更新答案
    maxSum = Math.max(maxSum, priceNewpath);

    // 返回节点的最大贡献值
    return node.val + Math.max(leftGain, rightGain);
  }
  maxGain(root);
  return maxSum;
}


// 输入两个字符数字,放回相乘结果
// 由于单个数字存放在数组中,能避免超大数字存放在数字类型中的精度损失
function Multiplication(s, t) {
  if (s == 0 || t == 0) return 0
  // 逆序存放结果
  let len = s.length - 1 + t.length - 1
  let res = new Array(s.length - 1 + t.length - 1).fill(0)
  for (let i = s.length - 1; i >= 0; i--) {
    let sign = 0
    for (let j = t.length - 1; j >= 0; j--) {
      let temp = s[i] * t[j] + sign + (res[len - i - j] || 0)
      let _rest = temp % 10
      sign = Math.floor(temp / 10)
      res[len - i - j] = _rest
    }
    if (res[len - i + 1] != undefined) {
      res[len - i + 1] += sign
    } else if (sign) {
      res[len - i + 1] = sign
    }
  }
  return res.reverse().join('')
}


// 有升序数组构建平衡二叉树
// 需要注意递归逻辑(没能独立想明白)
// make用于构造最小子树结构(当前节点,其左右子结点).孙子结点由子结点递归得出.结点本身不能参与传参,不然递归时将无法获取
function sortedArrayToBST(num) {
  function make(num, left, right) {
    if (left > right) return null
    let mid = Math.floor((left + right + 1) / 2)
    let node = new TreeNode(num[mid])
    node.left = make(num, left, mid - 1)
    node.right = make(num, mid + 1, right)
    return node
  }
  let index = Math.floor((num.length - 1) / 2)
  let root = new TreeNode(num[index])
  if (num.length == 0) return null
  return make(num, 0, num.length - 1);
}


// 由先序遍历和中序遍历结果逆向构建二叉树
// 注意点:
// 1. 先序遍历结果第一个一定是根节点.以此在中序结果中找出后可以大致判断左右子树两块
// 2. 根据中序结果的左子树结点数,在先序遍历中跳过相同数量的结点便可以找到右子树的根结点
// 3. 左子树的根结点应该可由先序遍历的根结点后续结点与中序结果中根结点左侧第一个是否相同判断(可以简化成先判断中序根左侧是否有结点,再根据先序根右侧第一个判断是什么)
// 4. 每次递归先序,后续结果都要缩减成以该节点为根的子树
function reConstructBinaryTree(pre, vin) {
  if (pre.length == 0) return
  let root = new TreeNode(pre[0])
  let j = vin.indexOf(pre[0])
  root.left = reConstructBinaryTree(pre.slice(1, j + 2), vin.slice(0, j))
  root.right = reConstructBinaryTree(pre.slice(j + 2), vin.slice(j + 1))

  return root
}


// 之形输出二叉树本质是bfs算法,只是输出时需要3个变量
// cur[] 保存当前层级的结点   next[] 保存下个层级的结点    level用于计算是否逆序输出当前层级的结点


// 将数字字符串转换成ip
// 每段要求[0,255] 同时不允许匹配到  /0\d*/ 即021,00等
// 本身不难,类似dfs,就是要求递归时要求数据还原
function restoreIpAddresses(s) {
  if (s.length < 4 || s.length > 16) return []
  let result = []

  function cal(s, path) {
    if (path.length == 3) {
      if (s[0] == '0') {
        if (s.length == 1) {
          result.push([...path, s])
        }
      } else if (parseInt(s) < 256) {
        result.push([...path, s])
      }
      return
    }
    for (let i = 1; i < 4; i++) {
      let ip = s.slice(0, i)
      if (ip[0] == '0' && ip.length > 1) {
        continue
      }
      if (parseInt(ip) < 256) {
        path.push(ip)
        cal(s.slice(i), path)
        path.pop()
      }
    }
  }
  cal(s, [])
  return result.map(ip => ip.join('.'))
}

// 返回[m,n]的数组
function makeArrane(m, n) {
  if (m > n) return makeArrane(n, m)
  return new Array(n - m + 1).fill(0).map((a, i) => i + m)
}
// 计算n!
function factorial(n, m = 1) {
  if (n == 1 || n == 0) return 1
  return makeArrane(n, m).reduce((a, b) => a * b)
}
// 计算(n,m)排列
function arrange(n, m) {
  if (n < m) return arrange(m, n)
  return makeArrane(n, n - m + 1).reduce((a, b) => a * b)
}
// 计算(n,m)组合
function combine(n, m) {
  if (n == m || m == 0) return 1
  if (n < m) return combine(m, n)
  if (m > n / 2) return combine(n, n - m)
  return arrange(n, m) / factorial(m)
}

// 用于删除指定路径,fs.rmdirSync只能删除空文件夹
const fs = require("fs")
const path = require("path")
str2.replace(/\/\s*/g, ',').split(',')
//  上面3行用于wallpaper
function deleteFolderRecursive(url) {
  var files = [];
  if (fs.existsSync(url)) {
    files = fs.readdirSync(url);
    files.forEach(function (file, index) {
      var curPath = path.join(url, file);
      // fs.statSync同步读取文件夹文件，如果是文件夹，在重复触发函数
      if (fs.statSync(curPath).isDirectory()) {
        deleteFolderRecursive(curPath);
      } else {
        fs.unlinkSync(curPath);
      }
    });
    fs.rmdirSync(url); // 清除文件夹
  } else {
    console.log("给定的路径不存在，请给出正确的路径");
  }
}